package com.cong._39;

import java.util.*;

class Solution {
    private List<List<Integer>> r;
    private int[] candidates;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        r = new LinkedList<>();
        recurComb(0, target, new LinkedList<>());

        return r;
    }
    private void recurComb(int index, int target, LinkedList<Integer> currentList) {
        if (index >= candidates.length) return;
        if (target <= 0) return;
        String tag = index +":" + target;
        if (candidates[index] == target) {
            List<Integer> l = new LinkedList<Integer>(currentList);
            l.add(candidates[index]);
            r.add(l);
        }

        recurComb(index + 1, target, currentList);
        currentList.add(candidates[index]);
        recurComb(index, target - candidates[index], currentList);
        currentList.removeLast();
    }
}
